// [2011统考真题]一个长度为L (L≥1)的升序序列S，处在第「L/27个位置的数称为S
// 的中位数。例如，若序列S1=(11,13, 15, 17,19)，则Sl的中位数是15，两个序列的中位
// 数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4, 6,8,20)，则S|和S2的中
// 位数是11。现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能
// 高效的算法，找出两个序列A和B的中位数。要求:
// 1)给出算法的基本设计思想。
// 2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
// 3)说明你所设计算法的时间复杂度和空间复杂度。

#pragma once
#include "vector"
#include "iostream"
template <typename ElemType>
void printVec(std::vector<ElemType> &vec)
{
    for (auto &i : vec)
    {
        std::cout << i << ",";
    }
    std::cout << "\r\n";
}
int findMiddleOfAB(const std::vector<int> &A, const std::vector<int> &B)
{
    int Abegin = 0, Aend = A.size() - 1, Amid;
    int Bbegin = 0, Bend = B.size() - 1, Bmid;
    while (Abegin != Aend || Bbegin != Bend)
    {
        Amid = (Abegin + Aend) / 2;
        Bmid = (Bbegin + Bend) / 2;
        int *smallBegin, *smallEnd, smallMid;
        int *bigBegin, *bigEnd, bigMid;
        // 为基数
        if (A[Amid] > B[Bmid])
        {
            bigBegin = &Abegin;
            bigEnd = &Aend;
            bigMid = Amid;
            smallBegin = &Bbegin;
            smallEnd = &Bend;
            smallMid = Bmid;
        }
        else
        {
            bigBegin = &Bbegin;
            bigEnd = &Bend;
            bigMid = Bmid;
            smallBegin = &Abegin;
            smallEnd = &Aend;
            smallMid = Amid;
        }
        *bigEnd = bigMid;
        if ((*smallBegin - *smallEnd + 1) % 2 == 0)
        {
            *smallBegin = smallMid + 1;
        }
        else
        {
            *smallBegin = smallMid;
        }
    }
    Amid = (Abegin + Aend) / 2;
    Bmid = (Bbegin + Bend) / 2;
    return A[Amid] < B[Bmid] ? A[Amid] : B[Bmid];
}
int main()
{
    std::cout << "hello \r\n";
    int arrA[] = {1, 2, 3, 4, 10, 11};
    int arrB[] = {5, 6, 7, 8};
    // std::vector<int> A =
    //     std::vector<int> B =
    std::vector<int> A(arrA, arrA + sizeof(arrA) / sizeof(int));
    std::vector<int> B(arrB, arrB + sizeof(arrB) / sizeof(int));

    printVec(A);
    printVec(B);

    std::cout << "middle is \r\n";
    std::cout << findMiddleOfAB(B, A) //;
              << "\r\n";
    // std::vector<int> vec1; // vec2, vec3;
    // int arr[100];
    // std::cout << "hello"
    //           << "\r\n";
    // //init data
    // for (int i = 0; i < 100; i++)
    // {
    //     arr[i] = i;
    // }
    // leftMoveArr(arr, 100, 30);

    // // fastFind(vec1, 9);
    // for (int i = 0; i < 100; i++)
    // {
    //     std::cout << arr[i] << ",";
    // }
    // std::cout << "\r\n";
    // for (int i = 0; i < vec2.size(); i++)
    // {
    //     std::cout << vec2[i] << ",";
    // }
    // std::cout << "\r\n";
    // ///////////////////////////////////////////////////
    // combineAB2C(vec1, vec2, vec3);
    // for (int i = 0; i < vec3.size(); i++)
    // {
    //     std::cout << vec3[i] << ",";
    // }
    // std::cout << "\r\n";
    return 0;
}